public class question_35 {
}
class Solution_350 {
    public int recursion(int nums[],int l,int r,int target){
//       递归终止条件，l==r
//        if(l==r){
//            if(nums[l]==target){
//                return l;
//            }
//            return nums[l]>target?l:l+1;
//        }
//        int mid=(l+r)/2;
//        if(nums[mid]==target){
//            return mid;
//        }
//        if(nums[mid]>target&&(mid-1)<l){
//            return l;
//        }
//        if(nums[mid]<target&&(mid+1)>r){
//            return r+1;
//        }
//        终止条件
        if(l>r){
            return l;
        }
        int mid=(l+r)/2;
        if(nums[mid]==target){
            return mid;
        }
        return nums[mid]>target?recursion(nums,l,mid-1,target):recursion(nums,mid+1,r,target);
    }

    public int searchInsert(int[] nums, int target) {
        return recursion(nums,0,nums.length-1,target);
    }

    public static void main(String[] args) {
        Solution_350 solution_350=new Solution_350();
        int arr[]={3,5,7,9,10};
        System.out.println(solution_350.searchInsert(arr, 8));
    }
}